package leetcode.hot100;

import java.util.ArrayList;
import java.util.List;

/**
 * 22. 括号生成
 * 输入：n = 3
 * 输出：["((()))","(()())","(())()","()(())","()()()"]
 *
 * @author: yjf
 * @date: 2024/12/2
 */
public class LeetCode22 {

    public static List<String> generateParenthesis(int n) {
        if (n == 0) {
            return new ArrayList<String>();
        }
        List<String> res = new ArrayList<>();
        process(new StringBuilder(), res, n, 0, 0);
        return res;
    }

    public static void process(StringBuilder sb, List<String> res, int n, int open, int close) {
        if (sb.length() == 2 * n) {
            res.add(sb.toString());
        } else {
            if (open < n) {
                sb.append('(');
                process(sb, res, n, open + 1, close);
                sb.deleteCharAt(sb.length() - 1);
            }
            if (close < open) {
                sb.append(')');
                process(sb, res, n, open, close + 1);
                sb.deleteCharAt(sb.length() - 1);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(generateParenthesis(3));
        // TODO 方法三:按括号序列的长度递归
        System.out.println(generate(3));
    }

    public static ArrayList[] cache = new ArrayList[100];

    public static List<String> generate(int n) {
        if (cache[n] != null) {
            return cache[n];
        }
        ArrayList<String> ans = new ArrayList<String>();
        if (n == 0) {
            ans.add("");
        } else {
            for (int c = 0; c < n; ++c) {
                for (String left: generate(c)) {
                    for (String right: generate(n - 1 - c)) {
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        cache[n] = ans;
        return ans;
    }
}
